package com.csx.base.core.algorithm.list;

import java.util.HashMap;

/**
 * <p> 请你设计并实现一个满足  LRU (最近最少使用) 缓存 约束的数据结构。
 *
 * <p> 实现 LRUCache 类：
 *
 * <p> LRUCache(int capacity) 以 正整数 作为容量 capacity 初始化 LRU 缓存
 *
 * <p> int get(int key) 如果关键字 key 存在于缓存中，则返回关键字的值，否则返回 -1 。
 * <p> void put(int key, int value) 如果关键字 key 已经存在，则变更其数据值 value ；
 * 如果不存在，则向缓存中插入该组 key-value 。
 * 如果插入操作导致关键字数量超过 capacity ，则应该 逐出 最久未使用的关键字。
 *
 * <p> 函数 get 和 put 必须以 O(1) 的平均时间复杂度运行。
 *
 * <p> 分析如下:
 *      get 和 put 的时间复杂度为 O(1),说明需要使用到hash表来存储数据才能保证放和取的时间复杂度
 *      但是又需要保证能淘汰掉最后使用的数据，那么也需要通过链表来存储数据，在数据达到指定容量时将链表最后的数据淘汰掉。在取数据时将数据重置到链表头，这个操作也要能保证O(1)才行
 * @author cuisongxu
 * @date 2024/3/3 周日 10:18
 */
public class LRUCache {

    public static void main(String[] args) {
//        LRUCache cache = new LRUCache(2);
//        cache.put(1,1);
//        cache.put(2,2);
//        int i1 = cache.get(1);
//        cache.put(3,3);
//        int i2 = cache.get(2);
//        cache.put(4,4);
//        int i3 = cache.get(1);
//        int i4 = cache.get(3);
//        int i5 = cache.get(4);
//        System.out.println(i1);
//        System.out.println(i2);
//        System.out.println(i3);
//        System.out.println(i4);
//        System.out.println(i5);

        LRUCache cache = new LRUCache(1);
        cache.put(2,1);
        int i1 = cache.get(2);
        cache.put(3,2);
        int i2 = cache.get(2);
        int i3 = cache.get(3);

        System.out.println(i1);
        System.out.println(i2);
        System.out.println(i3);
    }

    private final HashMap<Integer, DNode<Integer, Integer>> cache;

    private final DNode<Integer, Integer> first;

    private final DNode<Integer, Integer> last;

    private final int capacity;

    private int size = 0;

    public LRUCache(int capacity) {
        if(capacity <= 0) {
            throw new RuntimeException("缓存初始化容量不得小于等于0");
        }
        this.capacity = capacity;
        this.cache = new HashMap<>();
        this.first = new DNode<>();
        this.last = new DNode<>();
        first.next = last;
        last.prev = first;
    }

    public int get(int key) {
        DNode<Integer, Integer> node = cache.get(key);
        if(node == null) {
            return -1;
        }
        // 将当前访问的node移动到链表首位
        moveToHead(node);
        return node.value;
    }

    public void put(int key, int value) {
        DNode<Integer, Integer> node = cache.get(key);
        if(node == null) {
            node = new DNode<>(key, value);
            if (size >= capacity) {
                // 从缓存中移除最后一个
                cache.remove(last.prev.key);
                removeNode(last.prev);
                // 将新节点移动链表头部
                addToHead(node);
                // 加入缓存
                cache.put(key, node);
            }else {
                // 将新节点移动到链表头部
                addToHead(node);
                // 加入缓存
                cache.put(key, node);
                size ++;
            }

        }else {
            // 修改节点的值
            node.value = value;
            // 将新节点移动到链表头部
            moveToHead(node);

        }
    }

    private void removeNode(DNode<Integer, Integer> node) {
        node.prev.next = node.next;
        node.next.prev = node.prev;

    }

    private void addToHead(DNode<Integer, Integer> node) {
        node.prev = first;
        node.next = first.next;
        first.next.prev = node;
        first.next = node;
    }

    private void moveToHead(DNode<Integer, Integer> node) {
        removeNode(node);
        addToHead(node);
    }





    static class DNode<K,V> {

        public DNode<K,V> prev;
        public DNode<K,V> next;

        public K key;
        public V value;

        public DNode(K key, V value) {
            this.key = key;
            this.value = value;
        }

        public DNode() {

        }

    }
}
